#ifndef COUNTDOWN_H
#define COUNTDOWN_H

#include <sstream>
#include <string>
#include <vector>

std::string intToString(const int x) {
  std::ostringstream str;
  str << x;
  return str.str();
}

class CountdownSolution {

private:
  std::string solution;
  int value;

public:
  CountdownSolution() : solution(), value(0) {}

  CountdownSolution(const std::string &solutionIn, const int valueIn)
      : solution(solutionIn), value(valueIn) {}

  const std::string &getSolution() const { return solution; }

  int getValue() const { return value; }
};

// Do not edit above this line
double evaluateCountdown(const std::string &postfix) {
  std::vector<double> stack;
  std::istringstream iss(postfix);
  std::string token;

  if (postfix.empty()) {
    return 0.0;
  }

  while (iss >> token) {
    switch (token[0]) {
    case '+': {
      double a = stack.back();
      stack.pop_back();
      double b = stack.back();
      stack.pop_back();
      stack.push_back(a + b);
      break;
    }
    case '-': {
      double a = stack.back();
      stack.pop_back();
      double b = stack.back();
      stack.pop_back();
      stack.push_back(b - a);
      break;
    }
    case '*': {
      double a = stack.back();
      stack.pop_back();
      double b = stack.back();
      stack.pop_back();
      stack.push_back(a * b);
      break;
    }
    case '/': {
      double a = stack.back();
      stack.pop_back();
      double b = stack.back();
      stack.pop_back();
      stack.push_back(b / a);
      break;
    }
    default: {
      stack.push_back(std::stod(token));
      break;
    }
    }
  }
  return stack.back();
}

int pow(int number, int power) {
  int result = 1;
  for (int i = 0; i < power; ++i) {
    result *= number;
  }
  return result;
}

void searchChar(std::vector<std::vector<char>> &res,
                std::vector<char> &temp_perm, std::vector<bool> &chosen,
                std::vector<char> &arr) {
  if (temp_perm.size() == arr.size()) {
    res.push_back(temp_perm);
  } else {
    for (size_t i = 0; i < arr.size(); i++) {
      if (chosen[i] == true)
        continue;
      chosen[i] = true;
      temp_perm.push_back(arr[i]);
      searchChar(res, temp_perm, chosen, arr);
      chosen[i] = false;
      temp_perm.pop_back();
    }
  }
}

std::vector<std::vector<char>>
generate_permutations_char(std::vector<char> &arr) {
  std::vector<bool> chosen(arr.size() + 1);
  std::vector<std::vector<char>> permutations;
  std::vector<char> permutation;
  searchChar(permutations, permutation, chosen, arr);
  return permutations;
}

void search(std::vector<std::vector<int>> &res, std::vector<int> &temp_perm,
            std::vector<bool> &chosen, std::vector<int> &arr) {
  if (temp_perm.size() == arr.size()) {
    res.push_back(temp_perm);
  } else {
    for (size_t i = 0; i < arr.size(); i++) {
      if (chosen[i] == true)
        continue;

      chosen[i] = true;
      temp_perm.push_back(arr[i]);
      search(res, temp_perm, chosen, arr);
      chosen[i] = false;
      temp_perm.pop_back();
    }
  }
}

std::vector<std::vector<int>> generate_permutations(std::vector<int> &arr) {
  std::vector<bool> chosen(arr.size() + 1);
  std::vector<std::vector<int>> permutations;
  std::vector<int> permutation;
  search(permutations, permutation, chosen, arr);
  return permutations;
}

std::string toBinaryString(int number) {
  std::string res = "";
  while (number) {
    res += (number % 2) + '0';
    number /= 2;
  }
  res += std::string(6 - res.size(), '0');
  for (int i = 0; i < res.size() / 2; ++i) {
    std::swap(res[i], res[res.size() - 1 - i]);
  }
  return res;
}

std::vector<std::vector<int>> getSubsetValues(std::vector<int> &vec) {
  std::vector<std::vector<int>> subsets;

  for (int i = 0; i < pow(2, vec.size()); i++) {
    std::vector<int> subset;
    std::string selected = toBinaryString(i);
    for (int j = 0; j < vec.size(); j++) {
      if (selected[j] == '1') {
        subset.push_back(vec[j]);
      }
    }
    subsets.push_back(subset);
  }

  return subsets;
}

std::string merge_nums_with_operations(const std::vector<int> &nums,
                                       const std::vector<char> &operations) {
  std::string res = "";
  int j = 0, k = 0;
  for (size_t i = 0; i < (nums.size() + operations.size()); i++) {
    res += (i % 2 == 0) ? std::to_string(nums[j++])
                        : std::string(1, operations[k++]);
  }
  return res;
}

std::string merge_nums_with_operations_polish(std::vector<int> &nums,
                                              std::vector<char> &operations) {
  std::string res = "";

  for (size_t i = 0; i < nums.size(); i++) {
    res += std::to_string(nums[i]);
    res += " ";
  }
  for (int i = operations.size() - 1; i >= 0; i--) {
    res += operations[i];
    if (i != 0) {
      res += " ";
    }
  }

  return res;
}

CountdownSolution solveCountdownProblem(std::vector<int> &vec,
                                        const int &targetNumber) {
  std::string rpn = "";
  std::vector<char> vectorOfMathsOperations = {'+', '-', '*', '/'};
  std::vector<std::vector<char>> vectorOfSubsetsOfMathsOperations;

  std::vector<char> temp_operations = vectorOfMathsOperations;
  for (size_t i = 0; i < vectorOfMathsOperations.size(); i++) {
    temp_operations.push_back(vectorOfMathsOperations[i]);

    auto temp_subset_operation = generate_permutations_char(temp_operations);
    for (size_t j = 0; j < temp_subset_operation.size(); j++) {
      vectorOfSubsetsOfMathsOperations.push_back(temp_subset_operation[j]);
    }

    temp_operations.pop_back();
  }

  std::vector<std::vector<int>> vectorOfSubsetsFromVec = getSubsetValues(vec);

  double the_closest = 1e5;
  for (int i = 0; i < vectorOfSubsetsFromVec.size(); ++i) {
    std::vector<std::vector<int>> generatedPermutations =
        generate_permutations(vectorOfSubsetsFromVec[i]);
    for (int j = 0; j < generatedPermutations.size(); ++j) {
      for (size_t k = 0; k < vectorOfSubsetsOfMathsOperations.size(); k++) {
        if (vectorOfSubsetsOfMathsOperations[k].size() !=
            generatedPermutations[j].size() - 1) {
          continue;
        } else {
          if (generatedPermutations[j].size() == 0 ||
              vectorOfSubsetsOfMathsOperations[i].size() == 0) {
            continue;
          } else {
            double calculation =
                evaluateCountdown(merge_nums_with_operations_polish(
                    generatedPermutations[j],
                    vectorOfSubsetsOfMathsOperations[k]));
            if (std::abs(targetNumber - calculation) <
                std::abs(targetNumber - the_closest)) {
              the_closest = calculation;
              rpn = merge_nums_with_operations_polish(
                  generatedPermutations[j],
                  vectorOfSubsetsOfMathsOperations[k]);
            }
          }
        }
      }
    }
  }

  return CountdownSolution(rpn, the_closest);
}
// Do not edit below this line

#endif
